#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

#include "include/linked_list.h"
#include "include/stack.h"
#include "include/queue.h"
#include "Tree/binary_tree.h"
#include "heap.h"
#include "HashTable/simple_hashtable.h"
#include "DisjointSets/dsets.h"

#include "utils/random.h"
#include "utils/print_tree.h"


using namespace std;


void test_linked_list() {
    vector<int> nums{9, 7, 4, 8, 2, 3, 1};
    Node* list1 = create_list(nums);

    Node* ee = new Node(1);

    print(list1);
    delete_last_element(list1);
    remove(list1, 4);
    insert(list1, 10);
    insert_after(list1, 4, 12);
    print(list1);
    delete_first_element(list1);
    print(list1);

    cout << "start interleaving..." << endl;
    vector<int> vec2{1,2,3,4};
    vector<int> vec3{5,6,7,8,9};
    Node* list2 = create_list(vec2);
    Node* list3 = create_list(vec3);
    Node* res_list = interleave(list2, list3);
    print(res_list);
    print(to_vector(res_list));
    cout << endl;

    delete_list(list1);
    cout << (list1 == NULL) << endl;
    print(list1);
    delete ee;
}


void test_stack() {
    Stack<int> stk;
    stk.push(2);
    stk.push(5);
    stk.print();
    std::cout << stk.get_top() << std::endl;
    stk.pop();
    stk.pop();
    std::cout << stk.is_empty() << endl;
    stk.print();
}


void test_queue() {
    Queue<int> qu;
    qu.enqueue(1);
    qu.enqueue(2);
    cout << qu.size() << endl;
    qu.enqueue(3);
    cout << qu.is_full() << endl;
    qu.enqueue(4);
    qu.print();
    qu.dequeue();
    qu.dequeue();
    qu.dequeue();
    qu.dequeue();
    cout << qu.is_empty() << endl;
    qu.print();
}


void test_binary_tree() {
    util::usrand(98);
    BinaryTree<int> tree;
    cout << tree.height() << endl;
    tree.insert(5, false);
    tree.insert(3, false);
    tree.insert(6, false);
    cout << tree.is_ordered() << endl;
}


void test_heap() {
    // vector<int> numbers{3,2,5,4,1,9,6};
    int numbers[] = {3,2,5,4,1,9,6};
    Heap<int> heap(numbers, 7);
    cout << "heap size: " << heap.size() << endl;
    heap.print();
    heap.insert(7);
    heap.insert(-1);
    heap.print();
    cout << heap.get_min() << endl;
    heap.remove_top();
    heap.print();
    heap.remove_top();
    heap.print();
}


void test_simple_hashtable() {
    using namespace Simple;
    HashTable<int, int, HashFn> ht(8);
    ht.insert(5, 6);
    ht.insert(2, 3);
    ht.insert(9, 8);
//    ht.print();
//    int key = 5;
//    ht[5];
}


void test_dsets() {
    DisjointSets dsets;
    int n = 10;
    dsets.AddElements(n);
    for (int i=0; i<n; i++) {
        dsets.MakeSet(i);
    }
    dsets.Union(0,1);
    dsets.Union(1,2);
    dsets.Union(3,4);
    dsets.Union(6,9);
    dsets.Union(7,9);
    dsets.Union(8,9);
    dsets.Union(5,6);
    cout << dsets.Find(7) << endl;  // 6
    dsets.Union(1, 3);
    cout << dsets.Find(4) << endl;  // 0
    dsets.Union(9, 2);
    cout << dsets.Find(1) << endl;  // 6
}


int main() {
//    test_linked_list();
//    test_stack();
//    test_queue();
//    test_binary_tree();
//    test_heap();
//    test_simple_hashtable();
    test_dsets();
    return 0;
}
